{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Loud and Rich"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #graph #topological-sort #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #图 #拓扑排序 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: loudAndRich"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #喧闹和富有"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一组 <code>n</code> 个人作为实验对象，从 <code>0</code> 到 <code>n - 1</code> 编号，其中每个人都有不同数目的钱，以及不同程度的安静值（quietness）。为了方便起见，我们将编号为&nbsp;<code>x</code>&nbsp;的人简称为 \"person&nbsp;<code>x</code>&nbsp;\"。</p>\n",
    "\n",
    "<p>给你一个数组 <code>richer</code> ，其中 <code>richer[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> 表示 person&nbsp;<code>a<sub>i</sub></code>&nbsp;比 person&nbsp;<code>b<sub>i</sub></code>&nbsp;更有钱。另给你一个整数数组 <code>quiet</code> ，其中&nbsp;<code>quiet[i]</code> 是 person <code>i</code> 的安静值。<code>richer</code> 中所给出的数据 <strong>逻辑自洽</strong>（也就是说，在 person <code>x</code> 比 person <code>y</code> 更有钱的同时，不会出现 person <code>y</code> 比 person <code>x</code> 更有钱的情况 ）。</p>\n",
    "\n",
    "<p>现在，返回一个整数数组 <code>answer</code> 作为答案，其中&nbsp;<code>answer[x] = y</code>&nbsp;的前提是，在所有拥有的钱肯定不少于&nbsp;person&nbsp;<code>x</code>&nbsp;的人中，person&nbsp;<code>y</code>&nbsp;是最安静的人（也就是安静值&nbsp;<code>quiet[y]</code>&nbsp;最小的人）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]\n",
    "<strong>输出：</strong>[5,5,2,5,4,5,6,7]\n",
    "<strong>解释： </strong>\n",
    "answer[0] = 5，\n",
    "person 5 比 person 3 有更多的钱，person 3 比 person 1 有更多的钱，person 1 比 person 0 有更多的钱。\n",
    "唯一较为安静（有较低的安静值 quiet[x]）的人是 person 7，\n",
    "但是目前还不清楚他是否比 person 0 更有钱。\n",
    "answer[7] = 7，\n",
    "在所有拥有的钱肯定不少于 person 7 的人中（这可能包括 person 3，4，5，6 以及 7），\n",
    "最安静（有较低安静值 quiet[x]）的人是 person 7。\n",
    "其他的答案也可以用类似的推理来解释。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>richer = [], quiet = [0]\n",
    "<strong>输出：</strong>[0]\n",
    "</pre>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == quiet.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 500</code></li>\n",
    "\t<li><code>0 &lt;= quiet[i] &lt; n</code></li>\n",
    "\t<li><code>quiet</code> 的所有值 <strong>互不相同</strong></li>\n",
    "\t<li><code>0 &lt;= richer.length &lt;= n * (n - 1) / 2</code></li>\n",
    "\t<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt; n</code></li>\n",
    "\t<li><code>a<sub>i </sub>!= b<sub>i</sub></code></li>\n",
    "\t<li><code>richer</code> 中的所有数对 <strong>互不相同</strong></li>\n",
    "\t<li>对<strong> </strong><code>richer</code> 的观察在逻辑上是一致的</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [loud-and-rich](https://leetcode.cn/problems/loud-and-rich/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [loud-and-rich](https://leetcode.cn/problems/loud-and-rich/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]]\\n[3,2,5,4,6,1,7,0]', '[]\\n[0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        graph, degree, ans= defaultdict(list), [0] * len(quiet), [i for i in range(len(quiet))]\n",
    "\n",
    "        for x, y in richer:\n",
    "            graph[x].append(y)\n",
    "            degree[y] += 1\n",
    "        \n",
    "        queue = deque([i for i in range(len(quiet)) if not degree[i]])\n",
    "        while queue:\n",
    "            x = queue.popleft()\n",
    "            for y in graph[x]:\n",
    "                if quiet[ans[x]] < quiet[ans[y]]:\n",
    "                    ans[y] = ans[x]\n",
    "                degree[y] -= 1\n",
    "                if not degree[y]:\n",
    "                    queue.append(y)\n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        n = len(quiet)\n",
    "        poorer = [[] for _ in range(n)]\n",
    "        ingress = [0] * n\n",
    "        for r in richer:\n",
    "            poorer[r[0]].append(r[1])\n",
    "            ingress[r[1]] += 1\n",
    "        curr_richest = []\n",
    "        for i in range(n):\n",
    "            if not ingress[i]:\n",
    "                curr_richest.append(i)\n",
    "        res = [i for i in range(n)]\n",
    "\n",
    "        while curr_richest:\n",
    "            person = curr_richest.pop()\n",
    "            for person_poorer in poorer[person]:\n",
    "                if quiet[res[person_poorer]] > quiet[res[person]]:\n",
    "                    res[person_poorer] = res[person]\n",
    "                ingress[person_poorer] -= 1\n",
    "                if not ingress[person_poorer]:\n",
    "                    curr_richest.append(person_poorer)\n",
    "\n",
    "        # def dfs(p, min_quiet):\n",
    "        #     min_quiet_p = min_quiet[0]\n",
    "        #     min_quiet_v = min_quiet[1]\n",
    "        #     if min_quiet_v < quiet[res[p]]:\n",
    "        #         res[p] = min_quiet_p\n",
    "        #     for pn in poorer[p]:\n",
    "        #         if quiet[pn] < min_quiet_v:\n",
    "        #             dfs(pn, (pn, quiet[pn]))\n",
    "        #         else:\n",
    "        #             dfs(pn, min_quiet)\n",
    "        #\n",
    "        # for p in richest:\n",
    "        #     dfs(p, (p, quiet[p]))\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        N = len(quiet)\n",
    "        rich = collections.defaultdict(list)\n",
    "        for a, b in richer:\n",
    "            rich[b].append(a)\n",
    "        q_to_p = {q: i for i, q in enumerate(quiet)}\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i):\n",
    "            q = quiet[i]\n",
    "            for j in rich[i]:\n",
    "                q = min(q, dfs(j))\n",
    "            return q\n",
    "\n",
    "        return [q_to_p[dfs(i)] for i in range(N)]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "1. richer[i] = [a, b], a 比 b 有钱, 那么 answer[b] 依赖于 answer[a]\n",
    "2. 入度为 0 的节点 a, answer[a] = a, 因为此时 a 就是最有钱的人\n",
    "\n",
    "拓扑排序\n",
    "\n",
    "将入度为 0 的节点加入 队列q 中, answer[b] = min(answer[qi], quiet[y])\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        n = len(quiet)\n",
    "        ans = list(range(n))\n",
    "        # print(ans)\n",
    "        g = [[] for _ in range(n)]\n",
    "        deg = [0] * n\n",
    "\n",
    "        for a, b in richer:\n",
    "            g[a].append(b)\n",
    "            deg[b] += 1\n",
    "        \n",
    "        q = deque(i for i, d in enumerate(deg) if d == 0)\n",
    "\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            for y in g[x]:\n",
    "                # 更新更小的 quiet\n",
    "                if quiet[y] > quiet[x]:\n",
    "                    ans[y] = ans[x]\n",
    "                    quiet[y] = quiet[x]\n",
    "                deg[y] -= 1\n",
    "                if deg[y] == 0:\n",
    "                    q.append(y)\n",
    "            # print(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        # 闷声发大财\n",
    "        # 搜索：先序BFS\n",
    "        # 递推：dp[cur]=dp[pre]++\n",
    "        # 状态：边界节点：最富的人\n",
    "        # 每次更新邻接表节点的值\n",
    "        # 逻辑自洽，表示有向无环图\n",
    "        # if len(richer) == 0:\n",
    "        #     return quiet\n",
    "\n",
    "        # 建图：入度表和邻接表，从富有到贫穷\n",
    "        indeg = [0] * len(quiet)\n",
    "        neighbor = [[] for _ in range(len(quiet))]\n",
    "        for u,v in richer:\n",
    "            indeg[v] += 1\n",
    "            neighbor[u].append(v)\n",
    "        \n",
    "        ans = list(range(len(quiet))) # 初始值：都是自己\n",
    "        # 队列\n",
    "        queue = [i for i,deg in enumerate(indeg) if deg == 0]\n",
    "        while queue:\n",
    "            cur = queue.pop(0) # 出队\n",
    "            for next in neighbor[cur]:# 扩展\n",
    "                if quiet[ans[cur]] < quiet[ans[next]]:\n",
    "                    ans[next] = ans[cur]\n",
    "                indeg[next] -= 1\n",
    "                if indeg[next] == 0:# 入队\n",
    "                    queue.append(next)\n",
    "\n",
    "        return ans \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer, quiet):\n",
    "        \"\"\"\n",
    "        :type richer: List[List[int]]\n",
    "        :type quiet: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        m = collections.defaultdict(list)\n",
    "        for i, j in richer:\n",
    "            m[j].append(i)\n",
    "\n",
    "        res = [-1] * len(quiet)\n",
    "\n",
    "        def dfs(i):\n",
    "            if res[i] > 0: return res[i]\n",
    "            res[i] = i\n",
    "            for j in m[i]:\n",
    "                if quiet[res[i]] > quiet[dfs(j)]:\n",
    "                    res[i] = res[j]\n",
    "            return res[i]\n",
    "\n",
    "        for i in range(len(quiet)):\n",
    "            dfs(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        n = len(quiet)\n",
    "        answer = [None for i in range(n)]\n",
    "        parents = [[] for i in range(n)]\n",
    "        for rich in richer:\n",
    "            parents[rich[1]].append(rich[0])\n",
    "        # print(parents)\n",
    "        def dp(person: int) -> int:\n",
    "            nonlocal answer\n",
    "            if answer[person]:\n",
    "                return answer[person]\n",
    "            answer[person] = person\n",
    "            for parent in parents[person]:\n",
    "                t = dp(parent)\n",
    "                if quiet[t] < quiet[answer[person]]:\n",
    "                    answer[person] = t\n",
    "            return answer[person]\n",
    "        \n",
    "        for i in range(n):\n",
    "            dp(i)\n",
    "        return answer\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        graph = defaultdict(list)\n",
    "        indeg = [0] * len(quiet)\n",
    "        for x, y in richer:  # x is richer than y: x -> y\n",
    "            graph[x].append(y)\n",
    "            indeg[y] += 1\n",
    "        # topological sort\n",
    "        q = deque([i for i, d in enumerate(indeg) if d == 0])  # start from the richest\n",
    "        res = [i for i in range(len(quiet))]\n",
    "        while q:\n",
    "            rich = q.popleft()\n",
    "            for poor in graph[rich]:\n",
    "                if quiet[res[poor]] > quiet[res[rich]]:\n",
    "                    res[poor] = res[rich]\n",
    "                indeg[poor] -= 1\n",
    "                if indeg[poor] == 0:\n",
    "                    q.append(poor)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        # 拓扑排序，方向为富有指向贫穷\n",
    "        n = len(quiet)\n",
    "        poorDict = collections.defaultdict(list)\n",
    "        rich = [0] * n\n",
    "        for r in richer:\n",
    "            poorDict[r[0]].append(r[1])\n",
    "            rich[r[1]] += 1\n",
    "        \n",
    "        ans = [i for i in range(n)]\n",
    "        queue = [i for i in range(n) if rich[i] == 0]\n",
    "        while queue:\n",
    "            cur = queue.pop(0)\n",
    "            for new in poorDict[cur]:\n",
    "                if quiet[ans[cur]] < quiet[ans[new]]:\n",
    "                    ans[new] = ans[cur]\n",
    "                rich[new] -= 1\n",
    "                if rich[new] == 0:\n",
    "                    queue.append(new)\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        n = len(quiet)\n",
    "        g = [[] for _ in range(n)]\n",
    "        \n",
    "        inDeg = [0] * n\n",
    "        for r in richer:\n",
    "            g[r[0]].append(r[1])\n",
    "            inDeg[r[1]] += 1\n",
    "        ans = list(range(n))\n",
    "\n",
    "        q = deque(i for i, deg in enumerate(inDeg) if deg == 0)\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            for y in g[x] :\n",
    "                if quiet[ans[x]] < quiet[ans[y]]:\n",
    "                    ans[y] = ans[x]\n",
    "                inDeg[y] -= 1\n",
    "                if inDeg[y] == 0:\n",
    "                    q.append(y)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        n = len(quiet)\n",
    "        poorDict = collections.defaultdict(list)\n",
    "        rich = [0] * n\n",
    "        for r in richer:\n",
    "            poorDict[r[0]].append(r[1])\n",
    "            rich[r[1]] += 1\n",
    "        \n",
    "        ans = [i for i in range(n)]\n",
    "        queue = [i for i in range(n) if rich[i] == 0]\n",
    "        while queue:\n",
    "            cur = queue.pop(0)\n",
    "            for new in poorDict[cur]:\n",
    "                if quiet[ans[cur]] < quiet[ans[new]]:\n",
    "                    ans[new] = ans[cur]\n",
    "                rich[new] -= 1\n",
    "                if rich[new] == 0:\n",
    "                    queue.append(new)\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        n = len(quiet)\n",
    "\n",
    "        # 构建有向图\n",
    "        graph = [[] for _ in range(n)]\n",
    "\n",
    "        # 记录每个节点的入度\n",
    "        indegree = [0] * n\n",
    "\n",
    "        # 构建有向图和计算入度\n",
    "        for r in richer:\n",
    "            graph[r[0]].append(r[1])\n",
    "            indegree[r[1]] += 1\n",
    "\n",
    "        # 拓扑排序需要的队列\n",
    "        queue = []\n",
    "        l = 0\n",
    "        r = 0\n",
    "\n",
    "        # 找到入度为0的节点，加入队列\n",
    "        for i in range(n):\n",
    "            if indegree[i] == 0:\n",
    "                queue.append(i)\n",
    "                r += 1\n",
    "\n",
    "        # 初始化结果数组，每个节点的最安静的人就是自己\n",
    "        ans = [i for i in range(n)]\n",
    "\n",
    "        # 拓扑排序\n",
    "        while l < r:\n",
    "            cur = queue[l]\n",
    "            l += 1\n",
    "\n",
    "            # 遍历当前节点的邻居\n",
    "            for nxt in graph[cur]:\n",
    "                # 如果邻居的安静程度比当前节点小，则更新邻居的最安静的人\n",
    "                if quiet[ans[cur]] < quiet[ans[nxt]]:\n",
    "                    ans[nxt] = ans[cur]\n",
    "\n",
    "                # 将邻居的入度减一\n",
    "                indegree[nxt] -= 1\n",
    "\n",
    "                # 如果邻居的入度变为0，则加入队列\n",
    "                if indegree[nxt] == 0:\n",
    "                    queue.append(nxt)\n",
    "                    r += 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "# 示例用法\n",
    "sol = Solution()\n",
    "richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]]\n",
    "quiet = [3,2,5,4,6,1,7,0]\n",
    "result = sol.loudAndRich(richer, quiet)\n",
    "print(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        #拓扑排序\n",
    "        n=len(quiet)\n",
    "        graph=[[] for _ in range(n)]\n",
    "        degree=[0]*n\n",
    "        ans=[i for i in range(n)]\n",
    "        for u,v in richer:\n",
    "            graph[u].append(v)\n",
    "            degree[v]+=1\n",
    "        quene=[i for i in range(n) if degree[i]==0]\n",
    "        while quene:\n",
    "            x=quene.pop(0)\n",
    "            for y in graph[x]:\n",
    "                if quiet[ans[x]]<quiet[ans[y]]:\n",
    "                    ans[y]=ans[x]\n",
    "                degree[y]-=1\n",
    "                if degree[y]==0:\n",
    "                    quene.append(y)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        n = len(quiet)\n",
    "        g = [[] for _ in range(n)]\n",
    "        ans = list(range(n))\n",
    "        ind = [0] * n\n",
    "        for x, y in richer:\n",
    "            g[x].append(y)\n",
    "            ind[y] += 1\n",
    "        q = deque([i for i in range(n) if ind[i] == 0])\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            for y in g[x]:\n",
    "                ind[y] -= 1\n",
    "                if ind[y] == 0: q.append(y)\n",
    "                if quiet[ans[y]] > quiet[ans[x]]:\n",
    "                    ans[y] = ans[x]\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        q = []\n",
    "        res = [i for i in range(len(quiet))]\n",
    "        dic = {}\n",
    "        judge = [False] * len(quiet)\n",
    "        temp = [0] * len(quiet)\n",
    "        for edge in richer:\n",
    "            temp[edge[1]] += 1\n",
    "            if edge[0] not in dic:\n",
    "                dic[edge[0]] = [edge[1]]\n",
    "            else:\n",
    "                dic[edge[0]].append(edge[1])\n",
    "        flag = True\n",
    "        while flag:\n",
    "            flag = False\n",
    "            for i in range(len(quiet)):\n",
    "                if temp[i] == 0 and not judge[i]:\n",
    "                    flag = True\n",
    "                    judge[i] = True\n",
    "                    if i in dic:\n",
    "                        for j in dic[i]:\n",
    "                            if quiet[res[j]] > quiet[res[i]]:\n",
    "                                res[j] = res[i]\n",
    "                            temp[j] -= 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        n = len(quiet)\n",
    "        indg = [0] * n\n",
    "        rich = [[] for _ in range(n)]\n",
    "        queue = []\n",
    "        ans = [0] * n\n",
    "        for a, b in richer:\n",
    "            indg[b] += 1\n",
    "            rich[a].append(b)\n",
    "        for i in range(n):\n",
    "            ans[i] = i\n",
    "            if indg[i] == 0:\n",
    "                queue.append(i)\n",
    "        while queue:\n",
    "            temp = queue.pop(0)\n",
    "            for i in rich[temp]:\n",
    "                indg[i] -= 1\n",
    "                if quiet[ans[i]] > quiet[ans[temp]]:\n",
    "                    ans[i] = ans[temp]\n",
    "                if indg[i] == 0:\n",
    "                    queue.append(i)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        ans0 = [-2]*len(quiet)\n",
    "        ans = [-1]*len(quiet)\n",
    "        path = collections.defaultdict(list)\n",
    "        for a,b in richer:\n",
    "            path[b].append(a)\n",
    "        def dfs_min(x):\n",
    "            l = [quiet[x]]\n",
    "            for value in path[x]:\n",
    "                if ans[value] >= 0:\n",
    "                    l.append(ans0[value])\n",
    "                else:\n",
    "                    l.append(dfs_min(value))\n",
    "            ans0[x] = min(l)\n",
    "            return min(l)\n",
    "        for p in range(len(quiet)):\n",
    "            ans[p] = quiet.index(dfs_min(p))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# BFS \n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        n = len(quiet)\n",
    "        g = [[] for _ in range(n)]\n",
    "        ans = list(range(n))\n",
    "        ind = [0] * n\n",
    "        for x, y in richer:\n",
    "            g[x].append(y)\n",
    "            ind[y] += 1\n",
    "        q = deque([i for i in range(n) if ind[i] == 0])\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            for y in g[x]:\n",
    "                ind[y] -= 1\n",
    "                if ind[y] == 0: q.append(y)\n",
    "                if quiet[ans[y]] > quiet[ans[x]]:\n",
    "                    ans[y] = ans[x]\n",
    "        return ans\n",
    "\n",
    "# DFS \n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        n = len(quiet)\n",
    "        g = [[] for _ in range(n)]\n",
    "        ans = [-1] * n\n",
    "        for x, y in richer:\n",
    "            g[y].append(x)\n",
    "        def dfs(u):\n",
    "            if ans[u] != -1: return\n",
    "            ans[u] = u\n",
    "            for v in g[u]:\n",
    "                dfs(v)\n",
    "                if quiet[ans[v]] < quiet[ans[u]]:\n",
    "                    ans[u] = ans[v]\n",
    "        for i in range(n):\n",
    "            dfs(i)\n",
    "        return ans\n",
    "        \n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        graph = defaultdict(list)\n",
    "        for a,b in richer:\n",
    "            graph[b].append(a)\n",
    "        ans = []\n",
    "        n = len(quiet)\n",
    "        for i in range(n):\n",
    "            ans.append(i)\n",
    "            queue = deque([u for u in graph.get(i,[])])\n",
    "            visited = set()\n",
    "            while queue:\n",
    "                u = queue.popleft()\n",
    "                visited.add(u)\n",
    "                if quiet[ans[-1]] > quiet[u]:\n",
    "                    ans[-1] = u\n",
    "                for v in graph.get(u,[]):\n",
    "                    if v not in visited:\n",
    "                        queue.append(v)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        def neighbors(node, link):\n",
    "            ngs = []\n",
    "            for l in link:\n",
    "                if l[0] == node:\n",
    "                    ngs.append(l[1])\n",
    "            return ngs\n",
    "        \n",
    "        n = len(quiet)\n",
    "        richer = [[i[1], i[0]] for i in richer] # 重构连接图\n",
    "        father = [[] for i in range(n)] # 记录父节点\n",
    "        for l in richer:\n",
    "            father[l[1]].append(l[0])\n",
    "        answer = [i for i in range(n)]\n",
    "        stack = [] # 建栈，用于实现dfs\n",
    "        node = 0 # 起始点\n",
    "        while node != None:\n",
    "            n_quiet = quiet[node]\n",
    "            sons = neighbors(node, richer)\n",
    "            if len(sons) == 0:\n",
    "                f_nodes = father[node]\n",
    "                for f_node in f_nodes:\n",
    "                    if quiet[f_node] >= quiet[node]:\n",
    "                        quiet[f_node] = quiet[node]\n",
    "                        answer[f_node] = answer[node]\n",
    "                    if [f_node, node] in richer:\n",
    "                        richer.remove([f_node, node])\n",
    "                if node in stack:\n",
    "                    stack.remove(node)\n",
    "            stack.extend(sons)\n",
    "            if len(stack) != 0:\n",
    "                node = stack[-1]\n",
    "            elif len(richer) ==  0:\n",
    "                break\n",
    "            else:\n",
    "                node = richer[0][0]\n",
    "                stack.append(node)\n",
    "                \n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        n = len(quiet)\n",
    "        g = [[] for _ in range(n)]\n",
    "        indeg = [0] * n\n",
    "        for a, b in richer:\n",
    "            print(a, b)\n",
    "            g[a].append(b)\n",
    "            indeg[b] += 1\n",
    "        q = [i for i in range(n) if indeg[i] == 0]\n",
    "        ans = list(range(n))\n",
    "        while q:\n",
    "            a = q.pop(0)\n",
    "            for b  in g[a]: # a: rich, b:poor\n",
    "                if quiet[ans[b]] > quiet[ans[a]]:\n",
    "                    ans[b] = ans[a]\n",
    "                indeg[b] -= 1\n",
    "                if indeg[b] == 0:\n",
    "                    q.append(b)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "\n",
    "        n = len(quiet)\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        for r in richer: \n",
    "            g[r[1]].append(r[0])\n",
    "\n",
    "        print(g)\n",
    "        ans = [-1] * n\n",
    "\n",
    "        def dfs(x: int):\n",
    "            if ans[x] != -1:\n",
    "                return\n",
    "            ans[x] = x\n",
    "            for y in g[x]:\n",
    "                dfs(y)\n",
    "                if quiet[ans[y]] < quiet[ans[x]]:\n",
    "                    ans[x] = ans[y]\n",
    "\n",
    "        for i in range(n):\n",
    "            print(i)\n",
    "            dfs(i)\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich_DFS(self, richer: List[List[int]], quiet: List[int]) -> List[int]: # slow\n",
    "        def DFS(i):\n",
    "            nonlocal min_q\n",
    "            nonlocal min_i\n",
    "            if quiet[i] < min_q:\n",
    "                min_q = quiet[i]\n",
    "                min_i = i\n",
    "            nonlocal seen\n",
    "            seen.add(i)\n",
    "            for e in graph[i]:\n",
    "                if e not in seen:\n",
    "                    DFS(e)\n",
    "        \n",
    "        n = len(quiet)\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for dst, src in richer:\n",
    "            graph[src].append(dst)\n",
    "        #print(graph)\n",
    "        #ppppp\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            #print(i)\n",
    "            min_q = float('inf')\n",
    "            min_i = None\n",
    "            seen = set()\n",
    "            DFS(i)\n",
    "            ans.append(min_i)\n",
    "        return ans\n",
    "\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        n = len(quiet)\n",
    "        graph = [[] for _ in range(n)]\n",
    "        indegree = [0] * n\n",
    "        for src, dst in richer:\n",
    "            graph[src].append(dst)\n",
    "            indegree[dst] += 1\n",
    "\n",
    "        ans = list(range(n))\n",
    "        import queue\n",
    "        q = queue.deque([e for e in range(n) if indegree[e] == 0])\n",
    "        while q:\n",
    "            popped = q.popleft()\n",
    "            for e in graph[popped]:\n",
    "                if quiet[ans[e]] > quiet[ans[popped]]:\n",
    "                    #ans[e] = popped\n",
    "                    ans[e] = ans[popped]\n",
    "                indegree[e] -= 1\n",
    "                if indegree[e] == 0:\n",
    "                    q.append(e)\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        if not richer:\n",
    "            return [i for i in range(len(quiet))]\n",
    "\n",
    "        graph = defaultdict(list)\n",
    "        # 创建图结构，穷人指向富人，这确保是一个有向无环图\n",
    "        for r, p in richer:\n",
    "            graph[p].append(r)\n",
    "        # 创建一个优先队列，用来返回富人中更安静的人\n",
    "        q = []\n",
    "        visited = set()\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(u):\n",
    "            # if u in visited:\n",
    "            #     return \n",
    "            # visited.add(u)\n",
    "            ans = u\n",
    "            for v in graph[u]:\n",
    "                print(dfs(v))\n",
    "                if quiet[dfs(v)] < quiet[ans]:\n",
    "                    ans = dfs(v)\n",
    "            return ans\n",
    "        \n",
    "        res = []\n",
    "        for u in range(len(quiet)):\n",
    "            # ans = dfs(u)\n",
    "            res.append(dfs(u))\n",
    "            # q = []\n",
    "            # visited = set()\n",
    "\n",
    "        return res\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import *\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        edges = defaultdict(list)\n",
    "        for y, x in richer:\n",
    "            edges[x].append(y)\n",
    "        # 带记忆搜索的dfs\n",
    "        @lru_cache(None)\n",
    "        def dfs(x):\n",
    "            ansQ, ansY = quiet[x], x\n",
    "            for nextY in edges[x]:\n",
    "                curQuite, curY  = dfs(nextY)\n",
    "                if curQuite < ansQ:\n",
    "                    ansQ = curQuite\n",
    "                    ansY = curY\n",
    "            return ansQ, ansY\n",
    "        ans = []\n",
    "        for x in range(len(quiet)):\n",
    "            ansQ, ansY = dfs(x)\n",
    "            ans.append(ansY)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        def find_quiet(index):\n",
    "            queue = [index]\n",
    "            res_index = -1\n",
    "            res = float('inf')\n",
    "            visited = set()\n",
    "            while queue:\n",
    "                cur = queue.pop(0)\n",
    "                if res>quiet[cur]:\n",
    "\n",
    "                    res = quiet[cur]\n",
    "                    res_index = cur\n",
    "                visited.add(cur)\n",
    "                if cur in ref:\n",
    "                    richers = ref[cur]\n",
    "                    for r in richers:\n",
    "                        if r not in visited:\n",
    "                            queue.append(r)\n",
    "\n",
    "            return res_index\n",
    "        ref = collections.defaultdict(list)\n",
    "        n=len(quiet)\n",
    "        for rich, poor in richer:\n",
    "            ref[poor].append(rich)\n",
    "        # print(ref)\n",
    "        res = []\n",
    "\n",
    "        for i in range(n):\n",
    "            if i not in ref:\n",
    "                res.append(i)\n",
    "            else:\n",
    "                res.append(find_quiet(i))\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        n = len(quiet)\n",
    "        rich_dict = collections.defaultdict(list)\n",
    "        visited = set()\n",
    "        answer = [0]*n\n",
    "        res=[]\n",
    "        \n",
    "        for i,j in richer:\n",
    "            rich_dict[j].append(i)\n",
    "            \n",
    "        def dfs(pos): \n",
    "            res.append(pos)\n",
    "            visited.add(pos)          \n",
    "            for i in rich_dict[pos]:\n",
    "                if i not in visited:\n",
    "                    dfs(i)\n",
    "                            \n",
    "        for i in range(n):\n",
    "            dfs(i)\n",
    "            print(res)\n",
    "            val=float(\"inf\")\n",
    "            index = i\n",
    "            for j in res:\n",
    "                if val > quiet[j]:\n",
    "                    val = quiet[j]\n",
    "                    index = j\n",
    "            answer[i] = index\n",
    "            res = []\n",
    "            visited = set()\n",
    "        return answer\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "#         n = len(quiet)\n",
    "#         rich = [[]for _ in range(n)]\n",
    "#         for cur,pre in richer:\n",
    "#             rich[pre].append(cur)\n",
    "#         ans = [None]*n\n",
    "\n",
    "#         def dfs(i):\n",
    "#             if ans[i] is None:\n",
    "#                 ans[i] = i\n",
    "#             for j in rich[i]:\n",
    "#                 ind = dfs(j)\n",
    "#                 if quiet[ind]<quiet[ans[i]]:\n",
    "#                     ans[i]=ind\n",
    "#             return ans[i]\n",
    "#         return map(dfs,range(n))\n",
    "\n",
    "class Solution(object):\n",
    "    def loudAndRich(self, richer, quiet):\n",
    "        N = len(quiet)\n",
    "        graph = [[] for _ in range(N)]\n",
    "        for u, v in richer:\n",
    "            graph[v].append(u)\n",
    "\n",
    "        answer = [None] * N\n",
    "        def dfs(node):\n",
    "            #Want least quiet person in this subtree\n",
    "            if answer[node] is None:\n",
    "                answer[node] = node\n",
    "                for child in graph[node]:\n",
    "                    cand = dfs(child)\n",
    "                    if quiet[cand] < quiet[answer[node]]:\n",
    "                        answer[node] = cand\n",
    "            return answer[node]\n",
    "\n",
    "        return map(dfs, range(N))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        if not richer:\n",
    "            return [i for i in range(len(quiet))]\n",
    "\n",
    "        graph = defaultdict(list)\n",
    "        # 创建图结构，穷人指向富人，这确保是一个有向无环图\n",
    "        for r, p in richer:\n",
    "            graph[p].append(r)\n",
    "        # 创建一个优先队列，用来返回富人中更安静的人\n",
    "        q = []\n",
    "        visited = set()\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(u):\n",
    "            # if u in visited:\n",
    "            #     return \n",
    "            # visited.add(u)\n",
    "            ans = u\n",
    "            for v in graph[u]:\n",
    "                print(dfs(v))\n",
    "                if quiet[dfs(v)] < quiet[ans]:\n",
    "                    ans = dfs(v)\n",
    "            return ans\n",
    "        \n",
    "        res = []\n",
    "        for u in range(len(quiet)):\n",
    "            # ans = dfs(u)\n",
    "            res.append(dfs(u))\n",
    "            # q = []\n",
    "            # visited = set()\n",
    "\n",
    "        return res\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque, defaultdict\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        \"\"\"\n",
    "        :param richer:\n",
    "        :param quiet:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m2 = defaultdict(list)\n",
    "        for i in richer:\n",
    "            m2[i[1]].append(i[0])\n",
    "        @lru_cache(None)\n",
    "        def get_min(cur):\n",
    "            ans = quiet[cur]\n",
    "            idx = cur\n",
    "            for i in m2[cur]:\n",
    "                v1, idx2 = get_min(i)\n",
    "                if v1 < ans:\n",
    "                    idx = idx2\n",
    "                    ans = v1\n",
    "            return ans, idx\n",
    "        return [get_min(i)[1] for i in range(len(quiet))]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        n = len(quiet)\n",
    "        graph = defaultdict(list)\n",
    "        for a, b in richer:\n",
    "            graph[b].append(a)\n",
    "\n",
    "        @cache\n",
    "        def helper(i):\n",
    "            res, q = i, quiet[i]\n",
    "            for parent in graph[i]:\n",
    "                item = helper(parent)\n",
    "                if item[1] < q:\n",
    "                    res, q = item\n",
    "            return res, q\n",
    "\n",
    "        ans = [helper(i)[0] for i in range(n)]\n",
    "        helper.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        n = len(quiet)\n",
    "\n",
    "        table = [set() for _ in range(n)]\n",
    "        for a, b in richer:\n",
    "            table[b].add(a)\n",
    "\n",
    "        ret = [-1 for _ in range(n)]\n",
    "\n",
    "        def recur(curr):\n",
    "            if ret[curr] == -1:\n",
    "                ret[curr] = curr\n",
    "\n",
    "                for _next in list(table[curr]):\n",
    "                    recur(_next)\n",
    "\n",
    "                    if quiet[ret[_next]] < quiet[ret[curr]]:\n",
    "                        ret[curr] = _next\n",
    "                        for r in table[_next]:\n",
    "                            table[curr].add(r)\n",
    "                            if quiet[r] < quiet[ret[curr]]:\n",
    "                                ret[curr] = r\n",
    "\n",
    "        for i in range(n):\n",
    "            recur(i)\n",
    "\n",
    "        return ret        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        cache = {}\n",
    "        for ai, bi in richer:\n",
    "            g[bi].append(ai)\n",
    "        \n",
    "        def dfs(start):\n",
    "            if start in cache:\n",
    "                return cache[start]\n",
    "            val = quiet[start]\n",
    "            index = start            \n",
    "            visit[start] = True\n",
    "            # steps += 1\n",
    "            # if steps > 0 and val > quiet[start]:\n",
    "            #     val = quiet[start]\n",
    "            #     index = start\n",
    "            for end in g[start]:\n",
    "                if not visit[end]:\n",
    "                    v, idx = dfs(end)\n",
    "                    if v < val:\n",
    "                        val = v\n",
    "                        index = idx\n",
    "            visit[start] = False\n",
    "            cache[start] = (val, index)\n",
    "            return val, index\n",
    "\n",
    "        n = len(quiet)\n",
    "        visit = [False]*n\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            v, j = dfs(i)\n",
    "            ans.append(j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        dic=collections.defaultdict(set)\n",
    "        for i,j in richer:\n",
    "            dic[j].add(i)\n",
    "        \n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i):\n",
    "            q,idx=quiet[i],i \n",
    "            for j in dic[i]:\n",
    "                q1,idx1=dfs(j)\n",
    "                if q1<q:q,idx=q1,idx1\n",
    "            return q,idx\n",
    "        return [dfs(i)[1] for i in range(len(quiet))]\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def loudAndRich(self, richer, quiet):\n",
    "        N = len(quiet)\n",
    "        graph = [[] for _ in range(N)]\n",
    "        for u, v in richer:\n",
    "            graph[v].append(u)\n",
    "\n",
    "        answer = [None] * N\n",
    "        def dfs(node):\n",
    "            #Want least quiet person in this subtree\n",
    "            if answer[node] is None:\n",
    "                answer[node] = node\n",
    "                for child in graph[node]:\n",
    "                    cand = dfs(child)\n",
    "                    if quiet[cand] < quiet[answer[node]]:\n",
    "                        answer[node] = cand\n",
    "            return answer[node]\n",
    "\n",
    "        return map(dfs, range(N))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "val(x) = min(queitness, y) where y >= x\n",
    "graph. poorers are the dependencies. keep track of curr min_queitness guy at each node.\n",
    "'''\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        n = len(quiet)\n",
    "        poor_graph = defaultdict(set)\n",
    "        rich_degree = defaultdict(int)\n",
    "        quietest = list(range(n))\n",
    "        for rich, poor in richer:\n",
    "            poor_graph[rich].add(poor)\n",
    "            rich_degree[poor] += 1\n",
    "        \n",
    "        persons = deque([])\n",
    "        for person in range(n):\n",
    "            # no richers.\n",
    "            if rich_degree[person] == 0:\n",
    "                persons.append(person)\n",
    "        \n",
    "        while persons:\n",
    "            person = persons.popleft()\n",
    "            for poor in poor_graph[person]:\n",
    "                if quiet[quietest[person]] < quiet[quietest[poor]]:\n",
    "                    quietest[poor] = quietest[person]\n",
    "                rich_degree[poor] -= 1\n",
    "                if rich_degree[poor] == 0:\n",
    "                    persons.append(poor)\n",
    "            # print(person, quietest[person], quiet[quietest[person]])\n",
    "        \n",
    "        return quietest\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        # 构建有向图\n",
    "        # 递归寻找第 i 个最安静的人\n",
    "        n = len(quiet)\n",
    "        res = [-1] * n\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for x, y in richer:\n",
    "            graph[y].append(x)\n",
    "        \n",
    "        def _loudAndRich(i):\n",
    "            if res[i] > -1: return res[i]\n",
    "            res[i] = i\n",
    "            for j in graph[i]:\n",
    "                tmp = _loudAndRich(j)\n",
    "                if quiet[tmp] < quiet[res[i]]:\n",
    "                    res[i] = tmp\n",
    "            return res[i]\n",
    "\n",
    "        return map(_loudAndRich, range(n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        N = len(quiet)\n",
    "        tree = [[] for _ in range(N)]\n",
    "        for k,v in richer:\n",
    "            tree[v].append(k)\n",
    "            \n",
    "        answer = [-1]*N\n",
    "        def getmin(num):\n",
    "            if answer[num]==-1:\n",
    "                answer[num] = num\n",
    "                for child in tree[num]:\n",
    "                    richer = getmin(child)\n",
    "                    if quiet[richer] < quiet[answer[num]]:\n",
    "                         answer[num] = richer\n",
    "            return answer[num]\n",
    "        return map(getmin, range(N))\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque, defaultdict\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param richer:\n",
    "        :param quiet:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1 = defaultdict(list)\n",
    "        m2 = defaultdict(list)\n",
    "        for i in richer:\n",
    "            m1[i[0]].append(i[1])\n",
    "            m2[i[1]].append(i[0])\n",
    "        ret = []\n",
    "        @lru_cache(None)\n",
    "        def get_min(cur):\n",
    "            ans = quiet[cur]\n",
    "            idx = cur\n",
    "            for i in m2[cur]:\n",
    "                v1, idx2 = get_min(i)\n",
    "                if v1 < ans:\n",
    "                    idx = idx2\n",
    "                    ans = v1\n",
    "            return ans, idx\n",
    "        for i in range(len(quiet)):\n",
    "            ans1, idx = get_min(i)\n",
    "            ret.append(idx)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        d = defaultdict(dict)\n",
    "        for r in richer:\n",
    "            d[r[1]][r[0]] = 1\n",
    "        @lru_cache(None)\n",
    "        def cal(i):\n",
    "            res = [quiet[i],i]\n",
    "            for k in d[i].keys():\n",
    "                res = min(res,cal(k))\n",
    "            return res\n",
    "        return [cal(i)[1]for i in range(len(quiet))]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        n = len(quiet)\n",
    "        res = [-1] * n\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for x, y in richer:\n",
    "            graph[y].append(x)\n",
    "        \n",
    "        def _loudAndRich(i):\n",
    "            if res[i] > -1: return res[i]\n",
    "            res[i] = i\n",
    "            for j in graph[i]:\n",
    "                tmp = _loudAndRich(j)\n",
    "                if quiet[tmp] < quiet[res[i]]:\n",
    "                    res[i] = tmp\n",
    "            return res[i]\n",
    "\n",
    "        return map(_loudAndRich, range(n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        if richer is None:\n",
    "            return [min(quiet)]*len(quiet)\n",
    "        \n",
    "        temp = defaultdict(dict)\n",
    "        res = []\n",
    "        for i in range(len(quiet)):\n",
    "            temp[i][i]=quiet[i]\n",
    "            queue = []\n",
    "            for j in range(len(richer)):\n",
    "                if i==richer[j][1]:\n",
    "                    queue.append(richer[j])\n",
    "            while queue:\n",
    "                cur_rich,cur_poor = queue.pop()\n",
    "                temp[i][cur_rich] = quiet[cur_rich]\n",
    "                if cur_rich<i:\n",
    "                    temp[i].update(temp[cur_rich])\n",
    "\n",
    "                else:\n",
    "                    for k in range(len(richer)):\n",
    "                        if cur_rich==richer[k][1]:\n",
    "                            queue.append(richer[k])\n",
    "            res.append(min(temp[i],key=temp[i].get))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        connect = defaultdict(set)\n",
    "        for a, b in richer:\n",
    "            connect[b].add(a)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(x):\n",
    "            ans = x\n",
    "            for other in connect[x]:\n",
    "                if quiet[dfs(other)] < quiet[ans]:\n",
    "                    ans = dfs(other)\n",
    "\n",
    "            return ans\n",
    "        \n",
    "        return [dfs(i) for i in range(len(quiet))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        p = defaultdict(set)\n",
    "        r = defaultdict(set)\n",
    "        ps = set()\n",
    "        for x, y in richer:\n",
    "            p[x].add(y)\n",
    "            r[y].add(x)\n",
    "            ps.add(y)\n",
    "        rs = set(range(len(quiet))) - ps\n",
    "        d = {}\n",
    "        for i in range(len(quiet)):\n",
    "            d[i] = i   \n",
    "        while rs:\n",
    "            tmp = set()\n",
    "            for x in rs:\n",
    "                for y in p[x]:\n",
    "                    if quiet[d[y]] > quiet[d[x]]:\n",
    "                        d[y] = d[x]\n",
    "                    r[y].remove(x)\n",
    "                    if not r[y]:\n",
    "                        tmp.add(y)\n",
    "            rs = tmp\n",
    "        return [d[i] for i in range(len(quiet))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        from collections import defaultdict\n",
    "        graph = defaultdict(list)\n",
    "        for x, y in richer:\n",
    "            graph[y].append(x)\n",
    "        n = len(quiet)\n",
    "        res = [-1]*n\n",
    "        \n",
    "        def dfs(person):\n",
    "            if res[person] >= 0:\n",
    "                return res[person]\n",
    "            res[person] = person\n",
    "            for i in graph[person]:\n",
    "                if quiet[res[person]] > quiet[dfs(i)]:\n",
    "                    res[person] = res[i]\n",
    "            return res[person]\n",
    "        \n",
    "        for person in range(n):\n",
    "            dfs(person)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        n = len(quiet)\n",
    "        to = defaultdict(set)\n",
    "        outdgree = [0]*n\n",
    "        for i in richer:\n",
    "            to[i[0]].add(i[1])\n",
    "            outdgree[i[1]]+=1\n",
    "        queue = deque([])\n",
    "        for i in range(n):\n",
    "            if outdgree[i]==0:\n",
    "                queue.append(i)\n",
    "        res = [i for i in range(n)]\n",
    "        while queue:\n",
    "            x = queue.popleft()\n",
    "            for i in to[x]:\n",
    "                if quiet[res[x]]<quiet[res[i]]:\n",
    "                    res[i] = res[x]\n",
    "                outdgree[i]-=1\n",
    "                if not outdgree[i]:\n",
    "                    queue.append(i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        num_node = len(quiet)\n",
    "        graph = { i:set() for i in range(num_node)}\n",
    "        for x, y in richer:\n",
    "            # x richer than y\n",
    "            graph[y].add(x)\n",
    "        print(graph)\n",
    "        answer = list(range(num_node))\n",
    "        for i in range(num_node):\n",
    "            richers = graph[i]\n",
    "            while True:\n",
    "                temp = richers\n",
    "                for x in richers:\n",
    "                    temp = temp | graph[x]\n",
    "                if temp == richers:\n",
    "                    break;\n",
    "                richers = richers | temp\n",
    "            min_quiet = quiet[i]\n",
    "            index = i\n",
    "            for x in richers:\n",
    "                if quiet[x] < min_quiet:\n",
    "                    min_quiet = quiet[x]\n",
    "                    index = x\n",
    "            \n",
    "            answer[i] = index\n",
    "        return answer\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        connect, KEY = defaultdict(set), lambda y:quiet[y]\n",
    "        for a,b in richer:\n",
    "            connect[b].add(a)\n",
    "        @lru_cache(None)\n",
    "        def dfs(x):\n",
    "            return x if not connect[x] else min((x, min((dfs(o) for o in connect[x]), key=KEY)), key=KEY)\n",
    "        return [dfs(i) for i in range(len(quiet))]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        connect, KEY = defaultdict(set), lambda y:quiet[y]\n",
    "        for a,b in richer:\n",
    "            connect[b].add(a)\n",
    "        @lru_cache(None)\n",
    "        def dfs(x):\n",
    "            return x if not connect[x] else min((x, min((dfs(o) for o in connect[x]), key=KEY)), key=KEY)\n",
    "        return [dfs(i) for i in range(len(quiet))]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        from collections import defaultdict\n",
    "        graph = defaultdict(list)\n",
    "        for x, y in richer:\n",
    "            graph[y].append(x)\n",
    "        n = len(quiet)\n",
    "        res = [-1]*n\n",
    "        \n",
    "        def dfs(person):\n",
    "            if res[person] >= 0:\n",
    "                return res[person]\n",
    "            res[person] = person\n",
    "            for i in graph[person]:\n",
    "                if quiet[res[person]] > quiet[dfs(i)]:\n",
    "                    res[person] = res[i]\n",
    "            return res[person]\n",
    "        \n",
    "        for person in range(n):\n",
    "            dfs(person)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "\n",
    "        index_dict = {}\n",
    "        def dfs(p):\n",
    "            mines = quiet[p]\n",
    "            indexes = p\n",
    "            for i in range(m):\n",
    "                if g[p][i] == 1:\n",
    "                    if i in index_dict.keys():\n",
    "                        j,v = index_dict[i]\n",
    "                    else:\n",
    "                        j,v = dfs(i)\n",
    "                        index_dict[i] = [j,v]\n",
    "                    if v < mines:\n",
    "                        mines = v\n",
    "                        indexes = j\n",
    "            return indexes,mines\n",
    "\n",
    "        m = len(quiet)\n",
    "        if len(richer) == 0:\n",
    "            quiet.sort()\n",
    "            return quiet\n",
    "        else:\n",
    "\n",
    "            g = []\n",
    "            for i in range(m):\n",
    "                g.append([0] * m)\n",
    "            for item in richer:\n",
    "                g[item[1]][item[0]] = 1\n",
    "            ans = []\n",
    "\n",
    "            for i in range(m):\n",
    "                \n",
    "                j,v = dfs(i)\n",
    "\n",
    "                if i not in index_dict.keys():\n",
    "                    index_dict[i] = [j,v]\n",
    "\n",
    "                ans.append(j)\n",
    "            return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "sys.setrecursionlimit(1000000000)\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        n = len(quiet)\n",
    "        maps = [[False for _ in range(n)] for _ in range(n)]\n",
    "        quiets = []\n",
    "        for r in richer:\n",
    "            maps[r[0]][r[1]] = True\n",
    "        for i in range(n):\n",
    "            quiets.append((quiet[i], i))\n",
    "            maps[i][i] = True\n",
    "        quiets.sort(key=lambda x: x[0])\n",
    "        res = [None for i in range(n)]\n",
    "        def dfs(indx, anchor):\n",
    "            res[indx] = anchor\n",
    "            for i in range(n):\n",
    "                if maps[indx][i] and res[i] == None:\n",
    "                    dfs(i, anchor)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if maps[quiets[i][1]][j] and res[j] == None:\n",
    "                    dfs(j, quiets[i][1])\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        dic = defaultdict(set)\n",
    "        get_number = {s:i for i,s in enumerate(quiet)}\n",
    "        ans = []\n",
    "        #print(dic,'\\n',get_number)\n",
    "        for f,t in richer:\n",
    "            dic[t].add(f)\n",
    "        @cache\n",
    "        def dfs(key):\n",
    "            if key not in dic:\n",
    "                return quiet[key]\n",
    "            res = quiet[key]\n",
    "            for u in dic[key]:\n",
    "                res = min(res,dfs(u))\n",
    "            return res\n",
    "        for i in range(len(quiet)):\n",
    "            ans.append(get_number[dfs(i)])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        #mm[i][j]=1 表示j比i有钱\n",
    "        n=len(quiet)\n",
    "        mm=[[0 for i in range(n)] for i in range(n)]\n",
    "        for item in richer:\n",
    "            mm[item[1]][item[0]]=1\n",
    "        \n",
    "        dp=[[-1,-1] for i in range(n)]\n",
    "        def dfs(prenode):\n",
    "            ans=quiet[prenode]\n",
    "            minid=prenode\n",
    "            for i in range(n):\n",
    "                if mm[prenode][i]!=0:\n",
    "                    if dp[i][0]>=0:\n",
    "                        if dp[i][0]<ans:\n",
    "                            ans=dp[i][0]\n",
    "                            minid=dp[i][1]\n",
    "                    else:\n",
    "                        tmp=dfs(i)\n",
    "                        if tmp[0]<ans:\n",
    "                            ans=tmp[0]\n",
    "                            minid=tmp[1]\n",
    "                        #ans=min(ans,dfs(i))\n",
    "            dp[prenode]=[ans,minid]\n",
    "            return [ans,minid]\n",
    "        ret=[0 for i in range(n)]\n",
    "        for i in range(n):\n",
    "            ret[i]=dfs(i)[1]\n",
    "        return ret\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def get_anjing(self, i):\n",
    "        # 比我有钱的人中，最安静的那个已经计算过啦\n",
    "        if i in self.answer:\n",
    "            return self.answer[i]\n",
    "        # 没有比我更有钱的了，我就是最安静的那个仔\n",
    "        if i not in self.richer:\n",
    "            self.answer[i] = i\n",
    "            return i\n",
    "        _min = i\n",
    "        for biwo in self.richer[i]:\n",
    "            # 遍历比我有钱的人，找比他们还有钱的人的最安静的人\n",
    "            anjing = self.get_anjing( biwo)\n",
    "            # 再从这些人中找最安静的\n",
    "            if self.quiet[anjing] < self.quiet[_min]:\n",
    "                _min = anjing\n",
    "        self.answer[i] = _min\n",
    "        return _min\n",
    "    def loudAndRich(self, richer, quiet) :\n",
    "        # 把有钱人转换成字典\n",
    "        youqian = {}\n",
    "        for x, y in richer:\n",
    "            if y not in youqian:\n",
    "                youqian[y] = []\n",
    "            if x not in youqian[y]:\n",
    "                youqian[y].append(x)\n",
    "        # {人：部分比我有钱的人}\n",
    "        self.richer = youqian\n",
    "        # 安静值\n",
    "        self.quiet = quiet\n",
    "        # 答案字典\n",
    "        self.answer = {}\n",
    "        _len = len(quiet)\n",
    "        # 最后要求返回的是列表\n",
    "        _answer = []\n",
    "        for i in range(_len):\n",
    "            _answer.append(self.get_anjing(i))\n",
    "        return _answer\n",
    "\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def get_anjing(self, i):\n",
    "        # 比我有钱的人中，最安静的那个已经计算过啦\n",
    "        if i in self.answer:\n",
    "            return self.answer[i]\n",
    "        # 没有比我更有钱的了，我就是最安静的那个仔\n",
    "        if i not in self.richer:\n",
    "            self.answer[i] = i\n",
    "            return i\n",
    "        _min = i\n",
    "        for biwo in self.richer[i]:\n",
    "            # 遍历比我有钱的人，找比他们还有钱的人的最安静的人\n",
    "            anjing = self.get_anjing( biwo)\n",
    "            # 再从这些人中找最安静的\n",
    "            if self.quiet[anjing] < self.quiet[_min]:\n",
    "                _min = anjing\n",
    "        self.answer[i] = _min\n",
    "        return _min\n",
    "    def loudAndRich(self, richer, quiet) :\n",
    "        # 把有钱人转换成字典\n",
    "        youqian = {}\n",
    "        for x, y in richer:\n",
    "            if y not in youqian:\n",
    "                youqian[y] = []\n",
    "            if x not in youqian[y]:\n",
    "                youqian[y].append(x)\n",
    "        # {人：部分比我有钱的人}\n",
    "        self.richer = youqian\n",
    "        # 安静值\n",
    "        self.quiet = quiet\n",
    "        # 答案字典\n",
    "        self.answer = {}\n",
    "        _len = len(quiet)\n",
    "        # 最后要求返回的是列表\n",
    "        _answer = []\n",
    "        for i in range(_len):\n",
    "            _answer.append(self.get_anjing(i))\n",
    "        return _answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        mp = [[] for i in range(len(quiet))]\n",
    "        ru = [0 for i in range(len(quiet))]\n",
    "        for item in richer:\n",
    "            mp[item[1]].append([item[1], item[0]])\n",
    "            ru[item[0]] += 1\n",
    "        \n",
    "        \n",
    "        vis = [0 for i in range(len(quiet))]\n",
    "        a = [[0, 0] for i in range(len(quiet))]\n",
    "\n",
    "        def dfs(x):\n",
    "            if vis[x] == 1:\n",
    "                return a[x]\n",
    "            else:\n",
    "                vis[x] = 1\n",
    "\n",
    "            ans = x\n",
    "            minn = quiet[x]\n",
    "            for egde in mp[x]:\n",
    "\n",
    "                d = dfs(egde[1])\n",
    "              \n",
    "                if d[1] < minn:\n",
    "                    ans = d[0]\n",
    "                    minn = d[1]\n",
    "\n",
    "  \n",
    "            a[x] = [ans, minn]\n",
    "         \n",
    "            return [ans, minn]\n",
    "                \n",
    "\n",
    "\n",
    "        for i in range(len(quiet)):\n",
    "            if vis[i] == 0 and ru[i] == 0:\n",
    "                dfs(i)\n",
    "\n",
    "        return [i[0] for i in a]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        n = len(quiet)\n",
    "        richer_set = set(map(tuple,richer))\n",
    "        num_richer_dict = {}\n",
    "        for i in range(len(richer)):\n",
    "            a, b = richer[i]\n",
    "            if b not in num_richer_dict:\n",
    "                num_richer_dict[b] = [a]\n",
    "            else:\n",
    "                num_richer_dict[b].append(a)\n",
    "\n",
    "        for i in range(n):\n",
    "            # 对每个数i进行bfs\n",
    "            queue = [i]\n",
    "            visit = set()\n",
    "            while(queue):\n",
    "                cur = queue.pop()\n",
    "                if cur not in visit and cur in num_richer_dict:\n",
    "                    r_list = num_richer_dict[cur]\n",
    "                    # for r in r_list:\n",
    "                    #     if r not in\n",
    "                    queue.extend(r_list)\n",
    "                if cur not in visit:\n",
    "                    visit.add(cur)\n",
    "            num_richer_dict[i] = list(visit)\n",
    "\n",
    "        ans = [-1 for i in range(n)]\n",
    "        for k,v in num_richer_dict.items():\n",
    "            if not v:\n",
    "                ans[k] = k\n",
    "            else:\n",
    "                min_q = float('inf')\n",
    "                min_idx = 0\n",
    "                for man in v:\n",
    "                    if quiet[man] < min_q:\n",
    "                        min_q = quiet[man]\n",
    "                        min_idx = man\n",
    "                ans[k] = min_idx\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        num_node = len(quiet)\n",
    "        graph = { i:set() for i in range(num_node)}\n",
    "        for x, y in richer:\n",
    "            # x richer than y\n",
    "            graph[y].add(x)\n",
    "        answer = list(range(num_node))\n",
    "        for i in range(num_node):\n",
    "            richers = graph[i]\n",
    "            while True:\n",
    "                temp = richers\n",
    "                for x in richers:\n",
    "                    if not graph[x].issubset(richers):\n",
    "                        temp = temp | graph[x]\n",
    "                if temp == richers:\n",
    "                    break;\n",
    "                richers = richers | temp\n",
    "            \n",
    "            min_quiet = quiet[i]\n",
    "            index = i\n",
    "            for x in richers:\n",
    "                if quiet[x] < min_quiet:\n",
    "                    min_quiet = quiet[x]\n",
    "                    index = x\n",
    "            \n",
    "            answer[i] = index\n",
    "        return answer\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        richmap, n, inedges = collections.defaultdict(list), len(quiet), [0]*len(quiet)\n",
    "        res = [i for i in range(n)]\n",
    "        for u,v in richer:\n",
    "            richmap[u].append(v)\n",
    "            inedges[v]+=1\n",
    "        queue = collections.deque()\n",
    "        for i in range(n):\n",
    "            if inedges[i]==0: queue.append(i)\n",
    "\n",
    "        while queue:\n",
    "            for i in range(len(queue)):\n",
    "                people = queue.popleft()\n",
    "                for pospeople in richmap[people]:\n",
    "                    if quiet[people] < quiet[pospeople]:\n",
    "                        res[pospeople], quiet[pospeople] = res[people], quiet[people]\n",
    "                    inedges[pospeople]-=1\n",
    "                    if inedges[pospeople]==0: queue.append(pospeople)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        fathers = defaultdict(set)\n",
    "        for (a, b) in richer:\n",
    "            fathers[b].add(a)\n",
    "        n = len(quiet)\n",
    "        used = set()\n",
    "        def get_fathers(i: int, used: set):\n",
    "            res = i\n",
    "            Q = fathers[i]\n",
    "            while Q:\n",
    "                n = len(Q)\n",
    "                nxtQ = []\n",
    "                for x in Q:\n",
    "                    if x in used: continue\n",
    "                    used.add(x)\n",
    "                    if quiet[x] < quiet[res]: res = x\n",
    "                    nxtQ += fathers[x]\n",
    "                Q = nxtQ\n",
    "            return res\n",
    "\n",
    "        ans = list(range(n))\n",
    "        for i in range(n):\n",
    "            st = set()\n",
    "            ans[i] = get_fathers(i, st)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer, quiet):\n",
    "        numbers = len(quiet)\n",
    "        answer = [None for _ in range(numbers)]\n",
    "        _dict = {}\n",
    "        for _index in range(numbers):\n",
    "            _dict[_index] = _dict.get(_index, [])\n",
    "\n",
    "        for _ri, _po in richer:\n",
    "            if not _ri in _dict[_po]:\n",
    "                _dict[_po].append(_ri)\n",
    "\n",
    "        def dfs_find_quiet(person):\n",
    "            if answer[person] is not None:\n",
    "                return quiet[answer[person]]\n",
    "            quiet_value = quiet[person]\n",
    "            for _richer in _dict[person]:\n",
    "                quiet_value = min(quiet_value, dfs_find_quiet(_richer))\n",
    "            return quiet_value\n",
    "\n",
    "        for _index in range(numbers):\n",
    "            answer[_index] = quiet.index(dfs_find_quiet(_index))\n",
    "\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from copy import deepcopy\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        n = len(quiet)\n",
    "        nodes = [[] for _ in range(n)]\n",
    "        \n",
    "        for r in richer:\n",
    "            nodes[r[1]].append(r[0])\n",
    "            \n",
    "        \n",
    "        valid = [False] * n\n",
    "        def dfs(index):\n",
    "            \n",
    "            if valid[index]:\n",
    "                return nodes[index]\n",
    "            ret = deepcopy(nodes[index])\n",
    "            for next_index in nodes[index]:\n",
    "                ret.extend(dfs(next_index))\n",
    "            ret = list(set(ret))\n",
    "            nodes[index] = ret\n",
    "            valid[index] = True\n",
    "            return ret\n",
    "        \n",
    "        for i in range(n):\n",
    "            dfs(i)\n",
    "        \n",
    "        ans_q = deepcopy(quiet)\n",
    "        ans = list(range(n))\n",
    "        for i in range(n):\n",
    "            for j in nodes[i]:\n",
    "                if quiet[j] < ans_q[i]:\n",
    "                    ans_q[i] = quiet[j]\n",
    "                    ans[i] = j\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        if richer is None:\n",
    "            return [min(quiet)]*len(quiet)\n",
    "        richer.sort(key=lambda x:x[1])\n",
    "        temp = defaultdict(dict)\n",
    "        res = []\n",
    "        for i in range(len(quiet)):\n",
    "            temp[i][i]=quiet[i]\n",
    "            queue = []\n",
    "            for j in range(len(richer)):\n",
    "                if i==richer[j][1]:\n",
    "                    queue.append(richer[j])\n",
    "            while queue:\n",
    "                cur_rich,cur_poor = queue.pop()\n",
    "                temp[i][cur_rich] = quiet[cur_rich]\n",
    "                if cur_rich<i:\n",
    "                    temp[i].update(temp[cur_rich])\n",
    "\n",
    "                else:\n",
    "                    for k in range(len(richer)):\n",
    "                        if cur_rich==richer[k][1]:\n",
    "                            queue.append(richer[k])\n",
    "            res.append(min(temp[i],key=temp[i].get))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer, quiet):\n",
    "        numbers = len(quiet)\n",
    "        answer = [None for _ in range(numbers)]\n",
    "        _dict = {}\n",
    "        for _index in range(numbers):\n",
    "            _dict[_index] = _dict.get(_index, [])\n",
    "\n",
    "        for _ri, _po in richer:\n",
    "            if not _ri in _dict[_po]:\n",
    "                _dict[_po].append(_ri)\n",
    "\n",
    "        def dfs_find_quiet(person):\n",
    "            if answer[person] is not None:\n",
    "                return quiet[answer[person]]\n",
    "            quiet_value = quiet[person]\n",
    "            for _richer in _dict[person]:\n",
    "                quiet_value = min(quiet_value, dfs_find_quiet(_richer))\n",
    "            return quiet_value\n",
    "\n",
    "        for _index in range(numbers):\n",
    "            answer[_index] = quiet.index(dfs_find_quiet(_index))\n",
    "\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        n = len(quiet)\n",
    "        poorer = [[] for i in range(n)]\n",
    "        toper = set()\n",
    "        for x, y in richer:\n",
    "            poorer[x].append(y)\n",
    "            if y in toper: toper.remove(y)\n",
    "            toper.add(x)\n",
    "        ans = [i for i in range(n)]\n",
    "        while toper:\n",
    "            new_set = set()\n",
    "            for rich in toper:\n",
    "                for poor in poorer[rich]:\n",
    "                    if quiet[ans[poor]] > quiet[ans[rich]]:\n",
    "                        ans[poor] = ans[rich]\n",
    "                    new_set.add(poor)\n",
    "            toper = new_set\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        def dfs(idx):\n",
    "            nonlocal min_quiet, min_idx\n",
    "            for richer in graph[idx]:\n",
    "                if richer not in visited:\n",
    "                    visited.add(richer)\n",
    "                    if quiet[richer]<min_quiet:\n",
    "                        min_quiet = quiet[richer]\n",
    "                        min_idx = richer\n",
    "                    dfs(richer)\n",
    "        n = len(quiet)\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for i in richer:\n",
    "            graph[i[1]].append(i[0])\n",
    "        res = []\n",
    "        for i in range(len(quiet)):\n",
    "            min_quiet = quiet[i]\n",
    "            min_idx = i\n",
    "            visited = set()\n",
    "            dfs(i)\n",
    "            res.append(min_idx)\n",
    "        return res\n",
    "\"\"\"\n",
    "class Solution(object):\n",
    "    def loudAndRich(self, richer, quiet):\n",
    "        N = len(quiet)\n",
    "        graph = [[] for _ in range(N)]\n",
    "        for u, v in richer:\n",
    "            graph[v].append(u)\n",
    "\n",
    "        answer = [None] * N\n",
    "        def dfs(node):\n",
    "            #Want least quiet person in this subtree\n",
    "            if answer[node] is None:\n",
    "                answer[node] = node\n",
    "                for child in graph[node]:\n",
    "                    cand = dfs(child)\n",
    "                    if quiet[cand] < quiet[answer[node]]:\n",
    "                        answer[node] = cand\n",
    "            return answer[node]\n",
    "\n",
    "        return map(dfs, range(N))\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        if richer is None:\n",
    "            return [min(quiet)]*len(quiet)\n",
    "        richer.sort(key=lambda x:x[1])\n",
    "        temp = defaultdict(dict)\n",
    "        res = []\n",
    "        for i in range(len(quiet)):\n",
    "            temp[i][i]=quiet[i]\n",
    "            queue = []\n",
    "            for j in range(len(richer)):\n",
    "                if i==richer[j][1]:\n",
    "                    queue.append(richer[j])\n",
    "            while queue:\n",
    "                cur_rich,cur_poor = queue.pop()\n",
    "                temp[i][cur_rich] = quiet[cur_rich]\n",
    "                if cur_rich<i:\n",
    "                    temp[i].update(temp[cur_rich])\n",
    "\n",
    "                else:\n",
    "                    for k in range(len(richer)):\n",
    "                        if cur_rich==richer[k][1]:\n",
    "                            queue.append(richer[k])\n",
    "            res.append(min(temp[i],key=temp[i].get))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer, quiet):\n",
    "        \"\"\"\n",
    "        :type richer: List[List[int]]\n",
    "        :type quiet: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        from collections import defaultdict\n",
    "        graph = defaultdict(list)\n",
    "        for x, y in richer:\n",
    "            graph[y].append(x)\n",
    "        n = len(quiet)\n",
    "        res = [-1]*n\n",
    "        \n",
    "        def dfs(person):\n",
    "            if res[person] >= 0:\n",
    "                return res[person]\n",
    "            res[person] = person\n",
    "            for i in graph[person]:\n",
    "                if quiet[res[person]] > quiet[dfs(i)]:\n",
    "                    res[person] = res[i]\n",
    "            return res[person]\n",
    "        \n",
    "        for person in range(n):\n",
    "            dfs(person)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for u, v in richer:\n",
    "            g[v].append(u)\n",
    "\n",
    "        @cache\n",
    "        def getricher(i: int):\n",
    "            ans = []\n",
    "            for j in g[i]:\n",
    "                ans.append(j)\n",
    "                ans.extend(getricher(j))\n",
    "            return list(set(ans))\n",
    "\n",
    "        ans = []\n",
    "        n = len(quiet)\n",
    "        for i in range(n):\n",
    "            cur = getricher(i) + [i]\n",
    "            ans.append(min([x for x in cur], key=lambda q:quiet[q]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        graph=defaultdict(list)\n",
    "        for x,y in richer:\n",
    "            graph[y].append(x)\n",
    "        n=len(quiet)\n",
    "        res=[-1]*n\n",
    "        def dfs(person):\n",
    "            if res[person]>=0:\n",
    "                return res[person]\n",
    "            res[person]=person\n",
    "            for i in graph[person]:\n",
    "                if quiet[res[person]]>quiet[dfs(i)]:\n",
    "                    res[person]=res[i]\n",
    "            return res[person]\n",
    "        for person in range(n):\n",
    "            dfs(person)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        N= len(quiet)\n",
    "        dic = [[] for _ in range(N)]\n",
    "        for ri,poor in richer:\n",
    "            dic[poor].append(ri)\n",
    "        \n",
    "        res=[None]*N\n",
    "        def dfs(node):\n",
    "            if res[node] is None:\n",
    "                res[node]=node\n",
    "                for child in dic[node]:\n",
    "                    cand_node = dfs(child)\n",
    "                    if quiet[cand_node]<quiet[res[node]]:\n",
    "                        res[node]=cand_node\n",
    "            return res[node]\n",
    "\n",
    "\n",
    "        return list(map(dfs,range(N)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        person = defaultdict(list)\n",
    "        result = defaultdict(int)\n",
    "        reverse_quiet = defaultdict(int)\n",
    "        n = len(quiet)\n",
    "        for i in range(n):\n",
    "            person[i].append(i)\n",
    "            result[i] = quiet[i]\n",
    "            reverse_quiet[quiet[i]] = i\n",
    "        for x, y in richer:\n",
    "            person[y].append(x)\n",
    "\n",
    "        def find(x: int):\n",
    "            queue = deque(person[x])\n",
    "            visited = [x]\n",
    "            res = person[x]\n",
    "            while queue:\n",
    "                cur_x = queue.popleft()\n",
    "                if cur_x < x:\n",
    "                    result[x] = min(result[cur_x], result[x])\n",
    "                    continue\n",
    "                for temp in person[cur_x]:\n",
    "                    if temp not in visited:\n",
    "                        queue.append(temp)\n",
    "                        res.append(temp)\n",
    "                        visited.append(temp)\n",
    "                        if quiet[temp] < result[x]:\n",
    "                            result[x] = quiet[temp]\n",
    "\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            find(i)\n",
    "            ans.append(reverse_quiet[result[i]])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        person = defaultdict(list)\n",
    "        result = defaultdict(int)\n",
    "        reverse_quiet = defaultdict(int)\n",
    "        n = len(quiet)\n",
    "        for i in range(n):\n",
    "            person[i].append(i)\n",
    "            result[i] = quiet[i]\n",
    "            reverse_quiet[quiet[i]] = i\n",
    "        for x, y in richer:\n",
    "            person[y].append(x)\n",
    "\n",
    "        def find(x: int):\n",
    "            queue = deque(person[x])\n",
    "            visited = [x]\n",
    "            res = person[x]\n",
    "            while queue:\n",
    "                cur_x = queue.popleft()\n",
    "                if cur_x < x:\n",
    "                    result[x] = min(result[cur_x], result[x])\n",
    "                    continue\n",
    "                for temp in person[cur_x]:\n",
    "                    if temp not in visited:\n",
    "                        queue.append(temp)\n",
    "                        res.append(temp)\n",
    "                        visited.append(temp)\n",
    "                        if quiet[temp] < result[x]:\n",
    "                            result[x] = quiet[temp]\n",
    "\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            find(i)\n",
    "            ans.append(reverse_quiet[result[i]])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        link = {}\n",
    "        for a, b in richer:\n",
    "            if b not in link:\n",
    "                link[b] = []\n",
    "            link[b].append(a)\n",
    "            \n",
    "        m = {val: idx for idx, val in enumerate(quiet)}\n",
    "            \n",
    "        @lru_cache(typed=False, maxsize=128000000)\n",
    "        def solve(idx):\n",
    "            ans = quiet[idx]\n",
    "            if idx in link:\n",
    "                for next in link[idx]:\n",
    "                    ans = min(ans, solve(next))\n",
    "            return ans\n",
    "        \n",
    "        return [m[solve(idx)] for idx in range(len(quiet))]\n",
    "            \n",
    "    \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        tree = {i:{i} for i in range(len(quiet))}\n",
    "        for r in richer:\n",
    "            tree[r[1]].add(r[0])\n",
    "        \n",
    "        result = list(range(len(quiet)))\n",
    "        for i in range(len(quiet)):\n",
    "            buf = tree[i]\n",
    "            while buf:\n",
    "                nbuf = set()\n",
    "                for p in buf:\n",
    "                    if quiet[p] < quiet[result[i]]:\n",
    "                        result[i] = p\n",
    "                    nbuf |= tree[p]\n",
    "                nbuf -= buf\n",
    "                buf = nbuf\n",
    "            tree[i] |= buf\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        p2drs,n=defaultdict(list),len(quiet)\n",
    "        for (x,y) in richer:\n",
    "            p2drs[y].append(x)\n",
    "        answer=[None]*n\n",
    "        def dfs(node):\n",
    "            if answer[node] is None:\n",
    "                answer[node]=node\n",
    "                for child in p2drs[node]:\n",
    "                    cand=dfs(child) \n",
    "                    if quiet[cand]<quiet[answer[node]]: answer[node]=cand\n",
    "            return answer[node]           \n",
    "\n",
    "        return map(dfs,range(n))\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer, quiet):\n",
    "        n = len(quiet)\n",
    "        ans = [x for x in range(n)]\n",
    "        \n",
    "        rich_dict = defaultdict(list)\n",
    "        for x, y in richer:\n",
    "            rich_dict[y].append(x)\n",
    "        \n",
    "        for i in range(n):\n",
    "            if i not in rich_dict:\n",
    "                continue\n",
    "            stack = rich_dict[i][:]\n",
    "            min_quiet = quiet[i]\n",
    "            min_quiet_per = i\n",
    "            seen = {i}\n",
    "            while stack:\n",
    "                k = stack.pop()\n",
    "                if quiet[k] < min_quiet:\n",
    "                    min_quiet = quiet[k]\n",
    "                    min_quiet_per = k\n",
    "                if k in rich_dict:\n",
    "                    for j in rich_dict[k]:\n",
    "                        if j not in seen:\n",
    "                            stack.append(j)\n",
    "                            seen.add(j)\n",
    "            ans[i] = min_quiet_per\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        N = len(quiet)\n",
    "        graph = [[] for _ in range(N)]\n",
    "        for u, v in richer:\n",
    "            graph[v].append(u)\n",
    "\n",
    "        #answer = [i for i in range(N)]\n",
    "        answer = [None]*N \n",
    "        def dfs(node):\n",
    "            if answer[node] is None:\n",
    "                answer[node] = node\n",
    "                for child in graph[node]:\n",
    "                    cur_q = dfs(child)\n",
    "                    if quiet[cur_q] < quiet[answer[node]]:\n",
    "                        answer[node] = cur_q\n",
    "            return answer[node]\n",
    "\n",
    "        return map(dfs, range(N))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:\n",
    "        n = len(quiet)\n",
    "        mat = [[0] * n for _ in range(n)]\n",
    "        ret = [1000] * n \n",
    "        visited = [0] * n\n",
    "        for i in richer:\n",
    "            mat[i[1]][i[0]] = 1\n",
    "        def dfs(i):\n",
    "            res = i\n",
    "            if sum(mat[i]) == 0:\n",
    "                visited[i] = 1\n",
    "                ret[i] = res\n",
    "                return res\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 1:\n",
    "                    if visited[j] == 0:\n",
    "                        tmp = dfs(j)\n",
    "                    else:\n",
    "                        tmp = ret[j]\n",
    "                    if quiet[tmp] < quiet[res]:\n",
    "                        res = tmp\n",
    "            visited[i] = 1\n",
    "            ret[i] = res\n",
    "            return res\n",
    "        for i in range(n):\n",
    "            if visited[i] == 0:\n",
    "                dfs(i)    \n",
    "        return ret"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
